package com.practice.binarysearch;

/**
 * Given a row of animal cages, each animal needs fixed amount of water every day.
 * The cost to feed an animal equals needed water amount times distance from cage 
 * to water pipe. (A)
 * 
 * 1. Given one water pipe, find the best position to install this pipe to minimize
 * cost.
 * 
 * 2. Given two water pipes, find the best positions to install these pipes to
 * minimize the cost.
 */
public class AnimalCage {
	/**
	 * Returns optimized position to install one water pipe.
	 */
	public int optimizeOne(int[] amount) {
		Optimizer o = new Optimizer(amount);
		return o.solve();
	}
	
	/**
	 * Returns optimized positions to install two water pipes.
	 */
	public int[] optimizeTwo(int[] amount) {
		Optimizer o = new Optimizer(amount);
		return searchTwo(o, 0, amount.length-1);
	}
	
	private int[] searchTwo(Optimizer o, int lower, int upper) {
		int i = (lower + upper) / 2;
		int left = o.solve(0, i);
		int right = o.solve(i);

		if (lower == upper || left + right == 2*i) return new int[]{left, right};
		if (left + right > 2*i) {
			return searchTwo(o, i, upper);
		}
		else {
			return searchTwo(o, lower, i);
		}
	}
	
	private class Optimizer {
		private int			N;
		private int[]		s;
		
		private int			start;
		private int			end;
		
		public Optimizer(int[] amount) {
			N = amount.length;
			s = new int[N];
			s[0] = amount[0];
			for (int i=1; i<N; i++) {
				s[i] = s[i-1] + amount[i];
			}
		}
		
		/**
		 * Returns best position between 0..N-1.
		 */
		public int solve() {
			return solve(0, N-1);
		}
		
		public int solve(int start) {
			return solve(start, N-1);
		}
		
		/**
		 * Returns best position between start..end.
		 */
		public int solve(int start, int end) {
			this.start = start;
			this.end = end;
			return search(start, end);
		}
		
		private int search(int lower, int upper) {
			if (lower == upper) return lower;
			if (lower == upper-1) {
				return getLeft(lower)>=getRight(lower)? lower : upper;
			}
			
			int i = (lower + upper) / 2;
			int left = getLeft(i);
			int right = getRight(i);
			if (left == right) return i;
			
			if (left < right) {
				return search(i, upper);
			}
			else {
				return search(lower, i);
			}
		}
		
		private int getLeft(int index) {
			return start==0? s[index] : s[index] - s[start];
		}
		
		private int getRight(int index) {
			return s[end] - s[index];
		}
	}
}
